/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/letter-case-permutation
   @Language: C++
   @Datetime: 19-05-13 11:44
   */

class Solution {
	void backtrack(vector<string> &vs, string &s, int pos){
		if(pos>=s.length()) {
			vs.push_back(s);
			return;
		}
		if(isalpha(s[pos])){
			s[pos]=tolower(s[pos]);
			backtrack(vs,s,pos+1);
			s[pos]=toupper(s[pos]);
			backtrack(vs,s,pos+1);
		}
		else backtrack(vs,s,pos+1);
	}
public:
	/**
	 * @param S: a string
	 * @return: return a list of strings
	 */
	vector<string> letterCasePermutation(string &S) {
		// write your code here
		vector<string> vs;
		backtrack(vs,S,0);
		return vs;
	}
};
